package club.vann.nowcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <p>难度：Medium</p>
 * <p>题目：合并区间</p>
 * <p>描述：给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 * 示例1
 * 输入
 * 复制
 * [[10,30],[20,60],[80,100],[150,180]]
 * 返回值
 * 复制
 * [[10,60],[80,100],[150,180]]</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-21:21:05:01
 */
public class NC37 {
    public static void main(String[] args) {
        NC37 nc37 = new NC37();
        TestCase testCase = nc37.new TestCase();

        ArrayList<Interval> list = null;
        list = nc37.merge1(testCase.fun());
        list = nc37.merge1(testCase.fun1());
        System.out.println("Success");
    }

    /**
     * 解法一：
     *
     * @param intervals
     * @return
     */
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals == null || intervals.size() < 2) {
            return intervals;
        }

        PriorityQueue<Interval> queue = new PriorityQueue<Interval>(new Comparator<Interval>(){
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });

        for(Interval interval : intervals) {
            queue.add(interval);
        }

        ArrayList<Interval> ans = new ArrayList<>();
        Interval baseInterval = null;
        int start = Integer.MIN_VALUE;
        int end = Integer.MIN_VALUE;

        while(!queue.isEmpty()) {
            if(baseInterval == null) {
                baseInterval = queue.poll();
                start = baseInterval.start;
                end = baseInterval.end;
                continue;
            }

            Interval curInterval = queue.poll();
            if(end < curInterval.start) {
                ans.add(baseInterval);
                baseInterval = curInterval;
                start = baseInterval.start;
                end = baseInterval.end;
                continue;
            }

            end = Math.max(end, curInterval.end);
            baseInterval.end = end;
        }

        ans.add(baseInterval);
        return ans;
    }

    /**
     * 解法二：
     *
     * @param intervals
     * @return
     */
    public ArrayList<Interval> merge1(ArrayList<Interval> intervals) {
        ArrayList<Interval> ans = new ArrayList<>();
        Collections.sort(intervals, (a,b) -> {
            return a.start - b.start;
        });

        int len = intervals.size();
        int i = 0;
        while(i < len) {
            Interval interval = intervals.get(i);
            int start = interval.start;
            int end = interval.end;

            int j = i+1;
            while(j < len && intervals.get(j).start <= end) {
                end = Math.max(end, intervals.get(j).end);
                interval.end = end;
                j ++;
            }
            ans.add(interval);
            i = j;
        }
        return ans;
    }

    class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    class TestCase {
        public ArrayList<Interval> fun() {
            ArrayList<Interval> list = new ArrayList<>();
            list.add(new Interval(10, 30));
            list.add(new Interval(20, 60));
            list.add(new Interval(80, 100));
            list.add(new Interval(150, 180));
            return list;
        }

        public ArrayList<Interval> fun1() {
            ArrayList<Interval> list = new ArrayList<>();
            list.add(new Interval(10, 60));
            list.add(new Interval(20, 120));
            list.add(new Interval(50, 200));
            list.add(new Interval(70, 90));
            return list;
        }
    }
}
